문제 설명
어떤 문자열 s가 주어졌을 때, s로부터 만들 수 있는 부분 문자열 중 사전 순으로 가장 뒤에 나오는 문자열을 찾으려 합니다. 부분 문자열을 만드는 방법은 다음과 같습니다.
- s에서 일부 문자를 선택해 새로운 문자열을 만듭니다.
- 단, 이때 문자의 순서는 뒤바꾸지 않습니다.
예를 들어 문자열 xyb로 만들 수 있는 부분 문자열은 다음과 같습니다.
x y b xy xb yb xyb
이 중 사전 순으로 가장 뒤에 있는 문자열은 yb입니다.
문자열 s가 주어졌을 때 s로부터 만들 수 있는 부분 문자열 중 사전 순으로 가장 뒤에 나오는 문자열을 리턴하는 solution 함수를 완성해주세요.
제한 사항
- s는 길이가 1 이상 1,000,000 이하인 문자열입니다.
- s는 알파벳 소문자로만 이루어져 있습니다.
입출력 예
s | result |
---|---|
xyb | yb |
yxyc | yyc |
입출력 예 설명
입출력 예 #1
앞서 설명한 예와 같습니다.
입출력 예 #2
yxyc로 만들 수 있는 부분 문자열은 다음과 같습니다.
y x c yx yy yc xy xc yxy yxc yyc xyc yxyc
이 중 사전 순으로 가장 뒤에 나오는 문자열은 yyc입니다.
나의 풀이
첫번째 풀이
소스
def solution(s):
stack = []
for c in s:
if not stack:
stack.append(c)
continue
if stack[-1] < c:
stack.pop()
stack.append(c)
return ''.join(stack
설명
- Stack이용해서 마지막에 있는 문자열보다 새로들어오는 문자열이 크면 바꿔주는 방식 사용.
결과
일부분 틀림 (많이…)
리뷰
stack의 top에 해당하는 값이 c보다 작을 경우 계속 지워야 합니다. :)
edcbakjih
를 예로들면,
- edcba <- 여기까지 입력됩니다.
- edcba k <- top인 a가 k보다 작기 때문에 pop 됩니다.
- edcb k <- top인 b가 k보다 작기 때문에 pop 됩니다. …
- k <- k만 남습니다.
- kjih <- 그 이후로 k보다 큰 값은 안나오기 때문에 쭉 추가됩니다.
stack의 top에 해당하는 값이 c보다 작을 경우 계속 지워줘야 합니다.
while
을 이용하면 다음과 같이 코드를 작성할 수 있습니다.def solution(s): stack = [] for c in s: while stack and stack[-1] < c: stack.pop() stack.append(c) return ''.join(stack)
두번째 풀이
소스
def solution(s):
stack = []
for c in s:
while stack and stack[-1] < c:
stack.pop()
stack.append(c)
return ''.join(stack)
설명
- 리뷰 반영하여 작은것이 계속해서 있으면 계속해서 pop하는 방식으로 바꿨다.
결과
통과
스터디 리더의 풀이
def solution(s):
stack = []
for c in s:
while stack and stack[-1] < c:
stack.pop()
stack.append(c)
return ''.join(stack)